package com.atguigu.distributed.lock.leecode.dinamic;

import java.util.ArrayList;
import java.util.List;

public class DecodeWays {
    public List<String> decodeWays(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }

        // 使用动态规划存储中间结果
        @SuppressWarnings("unchecked")
        List<String>[] dp = new ArrayList[s.length() + 1];// 创建动态规划数组，索引从1开始
        dp[0] = new ArrayList<>();// 初始化dp数组第一个元素为空列表，表示空字符串的解码方式为一个空字符串
        dp[0].add("");

        // 遍历字符串
        for (int i = 1; i <= s.length(); i++) {
            dp[i] = new ArrayList<>();// 初始化dp数组的每个元素为一个空列表，用于存储当前索引位置的解码结果
            char currDigit = s.charAt(i - 1); // 获取当前数字字符

            // 尝试将当前数字作为单独一个字母
            if (currDigit != '0') {// 当前数字不为0时
                char currChar = (char) (currDigit - '1' + 'a');// 计算当前数字对应的字母
                for (String prevResult : dp[i - 1]) {// 遍历上一个位置的解码结果
                    dp[i].add(prevResult + currChar);// 将当前字母加到上一个位置的解码结果后面，得到当前位置的解码结果
                }
            }

            // 尝试将当前数字和前一个数字组合起来作为一个字母
            if (i > 1) {// 当前位置不为第一个位置时
                char prevDigit = s.charAt(i - 2);// 获取前一个数字字符
                int twoDigitNumber = Integer.parseInt(s.substring(i - 2, i));// 获取当前数字和前一个数字组成的两位数
                if (twoDigitNumber >= 10 && twoDigitNumber <= 26) {// 如果组合的两位数在10到26之间
                    char currChar = (char) (twoDigitNumber - 1 + 'a');// 计算组合的两位数对应的字母
                    for (String prevResult : dp[i - 2]) {// 遍历前两个位置的解码结果
                        dp[i].add(prevResult + currChar);// 将当前字母加到前两个位置的解码结果后面，得到当前位置的解码结果
                    }
                }
            }
        }

        return dp[s.length()];// 返回最终结果
    }
    public List<String> decodeWays2(String s){
        List<String> result = new ArrayList<>();
        if(s==null||s.length()==0){
            return result;
        }
        List<String>[] dp = new ArrayList[s.length()+1];//创建动态规划数组，索引从1开始
        dp[0] = new ArrayList<>();//初始化dp数组第一个元素为空列表，表示空字符串的解码方式为一个空字符串
        dp[0].add("");
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            dp[i] = new ArrayList<>();//初始化dp数组的每个元素为一个空列表，用于存储当前索引位置的解码结果
            char currDigit = s.charAt(i-1);//获取当前字符
            //尝试将当前数字作为单独一个字母
            if(currDigit!='0'){
                char currChar = (char)(currDigit-'1'+'a');//计算当前数字对应的字母
                for (String prevResult:dp[i-1]){
                    dp[i].add(prevResult+currChar);//将当前字母加到上一个位置的解码结果后面，得到当前位置的解码结果
                }
            }
            //尝试将当前数字和前一个数字组合起来作为一个字母
            if(i>1){//当前位置不为第一个位置时
                char preDigit = s.charAt(i-2);//获取前一个数字字符
                int twoDigitNumber = Integer.parseInt(s.substring(i-2,i));//获取当前数字和前一个数字组成的两位数
                char currChar = (char)(twoDigitNumber-1+'a');//计算组合的两位数字对应的字母
                for(String prevResult:dp[i-2]){//遍历前两个位置的解码结果
                    dp[i].add(prevResult+currChar);//将当前字母加到前两个位置的解码结果后面，得到当前位置的解码结果
                }
            }
        }
        return dp[s.length()];//返回最终结果

    }

    public static void main(String[] args) {
        DecodeWays decoder = new DecodeWays();
        List<String> result1 = decoder.decodeWays("11");
        System.out.println("输入 \"11\" 的译码结果：" + result1); // 输出: [aa, k]

        List<String> result2 = decoder.decodeWays("11325");
        System.out.println("输入 \"113\" 的译码结果：" + result2); // 输出: [aac, am, kc]
    }
}
